'''
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例:

输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-rectangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''

#思路一 我的暴力破解
'''
纯粹的暴力破解
先找出所有0点位置列表，再用一个函数判断当前矩形范围里面是否有0
时间复杂度（M^2N^2)


这个方法超时了，通过不了
'''


'''class Solution:
    def checkzero(self, x1, y1, x2, y2, zerolist):
        for i in range(x1, x2 + 1):
            for j in range(y1, y2 + 1):
                if (i, j) in zerolist:
                    return False
        return True

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if matrix == []:
            return 0
        m, n = len(matrix), len(matrix[0])
        zerolist = []
        maxlist = []
        maxarea = 0

        for i in range(0, m):
            for j in range(0, n):
                if matrix[i][j] == '0':
                    zerolist.append((i, j))
        print(zerolist)
        for x1 in range(0, m):
            for y1 in range(0, n):
                if (x1, y1) in zerolist:
                    continue
                for x2 in range(x1, m):
                    for y2 in range(y1, n):
                        if (Solution.checkzero(self, x1, y1, x2, y2, zerolist)):

                            area = (x2 - x1 + 1) * (y2 - y1 + 1)
                            if area >= maxarea:
                                maxlist = [(x1, y1), (x2, y2)]
                                maxarea = area
                        else:
                            break
        print(maxlist)
        return maxarea
'''

#思路二  暴力破解
'''
遍历每个点，求以这个点为矩阵右下角的所有矩阵面积。如下图的两个例子，橙色是当前遍历的点，然后虚线框圈出的矩阵是其中一个矩阵。

怎么找出这样的矩阵呢？如下图，如果我们知道了以这个点结尾的连续 1 的个数的话，问题就变得简单了。

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
得到：
1 0 1 0 0 
1 0 1 2 3 
1 2 3 4 5 
1 0 0 1 0 


1.首先求出高度是 1 的矩形面积，也就是它自身的数，如图中橙色的 4，面积就是 4。

2.然后向上扩展一行，高度增加一，选出当前列最小的数字，作为矩阵的宽，求出面积，对应上图的矩形框。
本质上在得到某一行某一列的连续1 个数时，固定这一列，不断向上寻找，上一行截止到这一列，有几个连续1，乘上上升的行数，得到最终面积

3.然后继续向上扩展，重复步骤 2。

'''

# class Solution:
#     def maximalRectangle(self, matrix: List[List[str]]) -> int:
#         if matrix is None or matrix[0] is None:
#             return 0
#         maxArea=0
#         width=[[]]*len(matrix)
'''这里不能使用乘法，否则会一起变化'''
#         width = [[],[],[],[]]
#         for i in range(0,len(matrix)):
#             for j in range(0,len(matrix[0])):
#                 if(matrix[i][j]=='1'):
#                     if j==0:
#                         width[i].append(1)
#                     else:
#                         width[i].append(width[i][j-1]+1)
#                 else:
#                     width[i].append(0)
#                 minWidth=width[i][j]
#                 for k in range(i,-1,-1):
#                     height=i-k+1
#                     minWidth=min(minWidth,width[k][j])
#                     maxArea=max(maxArea,minWidth*height)
#         return maxArea



#思路三，转换为最大矩形问题，将矩阵从上到下，分层看作多个柱状图，这样只需将高度传入函数，多次运行即可得到结果：
class Solution:
    def largestRectangleArea(self, heights):
        size = len(heights) + 2
        heights = [0] + heights + [0]
        stack = [0]
        res = 0

        for i in range(1, size):
            while heights[i] < heights[stack[-1]]:
                cur_height = heights[stack.pop()]  # 遇到比当前小的，根据入栈条件，可知当前柱高度大于左右两边的柱（右边柱紧邻，左边柱由栈顶位置确定），出栈
                cur_width = i - stack[-1] - 1  # 计算当前柱与栈顶（左边最近的柱）的距离
                res = max(res, cur_height * cur_width)
            stack.append(i)

        return res

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if matrix is None or matrix[0] is None:
            return 0
        maxArea=0
        height=[]
        for i in range(0,len(matrix)):
            height.append(0)
        for i in range(0,len(matrix)):
            for j in range(0,len(matrix[0])):
                if matrix[i][j]=="1":
                    height[j]+=1
                else:
                    height[j]=0
            maxArea=max(maxArea,Solution.largestRectangleArea(self,height))
            '''
            注意：是每计算完一行的高度，计算一次矩形面积
            '''
        return maxArea












